Significant attention has been paid to the analysis of social networks, particularly with respect to centrality measures. A centrality measure ranks nodes and/or edges in a given network based on the positional power of a node and/or edge or the influence of a node and/or edge over the network. Existing centrality measures, however, are often inadequate to satisfactorily serve the needs of emerging applications.
By way of illustration, consider an example that includes a computer network (such as, for instance, an intranet of a company) wherein the nodes represent workstations and the edges represent connections between the workstations. Also, assume that every workstation in the network can be potentially attacked by a virus which then propagates over the network. Additionally, consider a simple virus propagation model wherein an infected node infects all unprotected nodes (that is, those nodes without anti-virus software) that are reachable from the infected node. In such an example, if the virus spreads from an initial node chosen uniformly at random, a challenge arises in determining on which workstation(s) anti-virus software should be installed, given a limited amount resources.
By way of another example illustration, consider a scenario concerning the spread of misinformation over social media. Particularly, companies may rely on viral marketing of products to maximize revenue. However, in such instances, negative opinions as well as positive opinions may emerge and spread over a network of potential buyers. The company that owns this product will likely want to minimize the loss incurred due to the negative opinions. Therefore, a challenge exists in determining which individual buyers the company should target (for example, for additional convincing or promotion) in order to prevent a maximum number of other individuals from receiving a negative opinion.